import java.util.jar.JarEntry;

public class Sort {
    // 插入排序
public static void insertSort(int[] array){
       for(int i=0;i<array.length;i++){
           int tmp=array[i];
           int j=i;
           while(j>0 && tmp<array[j-1]){
               array[j]=array[j-1];
               j--;
           }
           array[j]=tmp;
       }
    }
        // 希尔排序
public static void shellSort(int[] array){
        int gap=array.length/2;
        for(;gap>=1;gap/=2){
            for(int i=gap;i<array.length;i++){
                int tmp=array[i];
                int j=i-gap;
                while(j>=0 && tmp<array[j]){
                    array[j+gap]=array[j];
                    j-=gap;
                }
                array[j+gap]=tmp;
            }
        }
    }
// 选择排序
public static void selectSort(int[] array){
       for(int i=0;i<array.length;i++){
           int tmp=array[i];
           int minindex=i;
           for(int j=i;j<array.length;j++){
               if(array[j]<array[minindex]) {
                   minindex=j;
               }
           }
           array[i]=array[minindex];
           array[minindex]=tmp;
       }
    }


// 堆排序
public static void heapSort(int[] array){
    int Size=array.length;
    int root=(Size-2)/2;
    for(;root>=0;root--){
        shiftDown(array,root,Size);
    }
    for(int i=Size-1;i>0;i--){
        int tmp=array[i];
        array[i]=array[0];
        array[0]=tmp;
        Size--;
        shiftDown(array,0,Size);
    }
 }

private static void shiftDown(int[] elem,int root,int len) {
        int parent=root;
        int child=root*2+1;
        while(child<len){
            if(child+1<len && elem[child+1]>elem[child]){
                child=child+1;
            }
            if(elem[parent]<elem[child]){
                int tmp=elem[parent];
                elem[parent]=elem[child];
                elem[child]=tmp;
            }else{
                break;
            }
            parent=child;
            child=2*parent+1;
        }
    }
    // 冒泡排序
public static void bubbleSort(int[] array){
       for(int i=1;i<array.length;i++){
           boolean flag=false;
           for(int j=0;j<array.length-i;j++){
               if(array[j]>array[j+1]){
                   int tmp=array[j];
                   array[j]=array[j+1];
                   array[j+1]=tmp;
                   flag=true;
               }
           }
           if(!flag) break;
       }
    }

// 快速
private static void swap(int[] array, int left, int right) {
    int tmp=array[left];
    array[left]=array[right];
    array[right]=tmp;
}
private static int partitionHare(int[] array, int left, int right) {
    int i=left;
    int j=right;
    int pivot=array[left];
    while(i<j){
        while(i<j && array[j]>=pivot){
            j--;
        }
        while(i<j && array[i]<=pivot){
            i++;
        }
        swap(array,i,j);
    }
    swap(array,left,i);
    return i;
}
private static int partition(int[] array, int left, int right) {
        int prev=left;
        int cur=prev+1;
        int pivot=array[left];
        while(cur<=right){
            if(array[cur]<pivot && array[prev]!=array[cur]){
                prev++;
                swap(array,cur,prev);
            }
            cur++;
        }
        swap(array,left,prev);
        return prev;
    }
private static int partitionhole(int[] array, int left, int right) {
        int i=left;
        int j=right;
        int pivot=array[left];
        while(i<j){
            while(i<j && array[j]>=pivot){
                j--;
            }
            array[i]=array[j];
            while(i<j && array[i]<=pivot){
                i++;
            }
            array[j]=array[i];
        }
        array[i]=pivot;
        return i;
    }
public static void quickSort(int[] array,int left,int right){
        if(left>=right) return;
        int partition=partition(array,left,right);
        quickSort(array,left,partition-1);
        quickSort(array,partition+1,right);
    }
public static void quickSort(int[] array){
    quickSort(array,0,array.length-1);
    }
}
